package com.example.binarytree;

import com.alibaba.fastjson.JSON;
import com.example.structure.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 构造二叉树
 */
public class BuildTree {

    /**
     * 106 中序后序构造
     * 让 postorder 成为全局变量，以免在递归方法中一直传递
     */
    private int[] postorder;
    private Map<Integer, Integer> hash;
    private int[] preorder;
    private Map<Integer, Integer> hash2;

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();
        buildTree.buildTreePost(new int[]{1, 2, 3}, new int[]{1});
    }

    public TreeNode buildTreePost(int[] inorder, int[] postorder) {
        int inLen = inorder.length;
        int postLen = postorder.length;

        if (inLen != postLen) {
            return null;
        }
        this.postorder = postorder;
        hash = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            hash.put(inorder[i], i);
        }
        return buildTreePost(0, inLen - 1, 0, postLen - 1);
    }

    /**
     * 使用中序遍历序列 inorder 的子区间 [inLeft, inRight]
     * 与后序遍历序列 postorder 的子区间 [postLeft, postRight] 构建二叉树
     *
     * @param inLeft    中序遍历序列的左边界
     * @param inRight   中序遍历序列的右边界
     * @param postLeft  后序遍历序列的左边界
     * @param postRight 后序遍历序列的右边界
     * @return 二叉树的根结点
     */
    private TreeNode buildTreePost(int inLeft, int inRight, int postLeft, int postRight) {
        if (inLeft > inRight || postLeft > postRight) {
            return null;
        }
        int pivot = postorder[postRight];
        int pivotIndex = hash.get(pivot);
        TreeNode root = new TreeNode(pivot);
        root.left = buildTreePost(inLeft, pivotIndex - 1, postLeft, postRight - inRight + pivotIndex - 1);
        root.right = buildTreePost(pivotIndex + 1, inRight, postRight - inRight + pivotIndex, postRight - 1);
        return root;
    }

    /**
     * 105 中序前序构造
     */
    public TreeNode buildTreePre(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if (preLen != inLen) {
            return null;
        }
        this.preorder = preorder;
        this.hash = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            hash.put(inorder[i], i);
        }
        return buildTreePre(0, preLen - 1, 0, inLen - 1);
    }


    private TreeNode buildTreePre(int preLeft, int preRight, int inLeft, int inRight) {
        // 因为是递归调用的方法，按照国际惯例，先写递归终止条件
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        // 先序遍历的起点元素很重要
        int pivot = preorder[preLeft];
        TreeNode root = new TreeNode(pivot);
        int pivotIndex = hash.get(pivot);
        root.left = buildTreePre(preLeft + 1, pivotIndex - inLeft + preLeft, inLeft, pivotIndex - 1);
        root.right = buildTreePre(pivotIndex - inLeft + preLeft + 1, preRight, pivotIndex + 1, inRight);
        return root;
    }
}

/**
 * 654. 最大二叉树
 * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 * <p>
 * 二叉树的根是数组 nums 中的最大元素。
 * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 返回有给定数组 nums 构建的 最大二叉树 。
 */
class ConstructMaximumBinaryTree {
    static int[] nums;

    public static TreeNode construct(int l, int r) {
        if (l == r) return null;
        int max = maxIndex(l, r);
        TreeNode root = new TreeNode(nums[max]);
        root.left = construct(l, max);
        root.right = construct(max + 1, r);
        return root;
    }

    /**
     * 返回区间内的最大值的索引
     */
    public static int maxIndex(int l, int r) {
        int max = l;
        for (int i = l; i < r; i++) {
            if (nums[max] < nums[i])
                max = i;
        }
        return max;
    }

    public static void main(String[] args) {
        ConstructMaximumBinaryTree constructMaximumBinaryTree = new ConstructMaximumBinaryTree();
        System.out.println(JSON.toJSONString(constructMaximumBinaryTree.constructMaximumBinaryTree(new int[]{1, 2, 3, 4})));
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return construct(0, nums.length);
    }
}